CODE 109. Merge k Sorted Lists

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/11/05/2013-11-05-CODE 109 Merge k Sorted Lists/

访问原文「CODE 109. Merge k Sorted Lists」

Merge k sorted
linked lists and return it as one sorted list. Analyze and describe its complexity.

public ListNode mergeKLists(ArrayList<ListNode> lists) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	if (null == lists || lists.isEmpty()) {
		return null;
	}
	return dfs(lists, 0, lists.size() - 1);
}

ListNode dfs(ArrayList<ListNode> lists, int start, int end) {
	if (start == end) {
		return lists.get(start);
	} else if (end > start && end == start + 1) {
		return merge2Lists(lists.get(start), lists.get(end));
	}
	int mid = start + (end - start) / 2;
	ListNode left = dfs(lists, start, mid);
	ListNode right = dfs(lists, mid + 1, end);
	return merge2Lists(left, right);
}

ListNode merge2Lists(ListNode first, ListNode second) {
	ListNode tmpF = first;
	ListNode tmpS = second;
	ListNode newNode = new ListNode(0);
	ListNode tmpN = newNode;
	while (null != tmpF && null != tmpS) {
		if (tmpS.val >= tmpF.val) {
			tmpN.next = tmpF;
			tmpF = tmpF.next;
			tmpN = tmpN.next;
		} else {
			ListNode node = new ListNode(tmpS.val);
			tmpN.next = node;
			tmpS = tmpS.next;
			tmpN = tmpN.next;
		}
	}
	if (null != tmpS) {
		tmpN.next = tmpS;
	}
	if (null != tmpF) {
		tmpN.next = tmpF;
	}
	return newNode.next;
}